/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-03-31 10:54:27
 * @LastEditors: lily
 * @LastEditTime: 2021-04-15 11:23:43
 */
/*
 * @lc app=leetcode.cn id=15 lang=javascript
 *
 * [15] 三数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */

//  思路：双指针法
//  对数组进行排序，后固定一个数 nums[curr]，再使用左右指针指向 nums[curr] 后面的两端，计算三个数的和是否为 0，满足则添加进结果集。
//  链接：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/

//  复杂度：O(n2)  O(logn)数组排序的复杂度，此处直接修改了原数组

var threeSum = function (nums) {
    let len = nums.length, res = []
    if (len < 3) return res

    // 排序，sort会改变原数组
    nums.sort((a, b) => a - b);

    for (let curr = 0; curr < len; curr++) {
        let head = curr + 1, tail = len - 1
        // 当前值为最小值（因为已排序），如果其>0，就不存在三元组 结束循环
        if (nums[curr] > 0) break
        // 当前元素去重
        // 如果相等，说明该数字重复，会导致结果重复，所以跳过
        if (nums[curr - 1] === nums[curr]) continue

        // 当头指针超过尾指针，跳出循环
        while (head < tail) {
            let sum = nums[curr] + nums[head] + nums[tail]
            if (sum === 0) {
                res.push([nums[curr], nums[head], nums[tail]])
                // head tail去重
                while (nums[head] === nums[head + 1]) head++
                while (nums[tail] === nums[tail - 1]) tail--
                head++
            } else if (sum < 0) {
                head++
            } else {
                tail--
            }
        }

    }
    return res
};
// @lc code=end

console.log(threeSum([-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6]));